# 插入搜索位置： https://leetcode-cn.com/problems/search-insert-position/

class Solution:
    def searchInsert(self, nums: list, target: int) -> int:
        """
            就是二分查找
            搞清楚插入位置就行了。 如果大于最后剩的元素就插它后面， 否则就放到它前面，下标就是mid的下标。
        """

        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                return mid
        
        return mid + 1 if target > nums[mid] else mid

